package hyy_2022;

import commons.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 获取两个链表的相交结点
 */
public class _0713_160_Offer52_IntersectionNode {

    /**
     * 两个链表的第一个公共节点
     * 1、首先遍历链表headA,并将链表headA中的每个节点加入哈希集合中
     * 2、然后遍历链表headB,对于遍历到的每个节点,判断该节点是否在哈希集合中
     *      如果当前节点不在哈希集合中,则继续遍历下一个节点
     *      如果当前节点在哈希集合中,即从当前节点开始的所有节点都是两个链表的公共节点
     * 3、结论：在链表headB中遍历到的第一个在哈希集合中的节点就是两个链表的第一个公共节点
     * @param headA
     * @param headB
     * @return ListNode 返回公共节点
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }

        //遍历链表headA,将链表headA中节点加入到哈希集合中
        Set<ListNode> set = new HashSet<>();
        ListNode temp = headA;
        while(temp != null) {
            set.add(temp);
            temp = temp.next;
        }

        //然后遍历链表headB,并判断遍历到的每个节点,是否存在哈希集合中
        temp = headB;
        while(temp != null) {
            if(set.contains(temp)) {
                return temp;
            }
            temp = temp.next;
         }
        return null;
    }
}
